package com.cy.linklist;

/**
 * @Author: chenyun
 * @Date: 2021/09/22/17:12
 * @Description:
 */
//142. 环形链表 II

import java.util.HashSet;

/**
 * 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 */
public class Demo142 {

    //解法一：借助HashSet
    //时间复杂度O(N),空间复杂度O(N)
    public ListNode detectCycle1(ListNode head) {
        HashSet<ListNode> set =  new HashSet<ListNode>();
        while(head != null){
            if(set.add(head)){
                head = head.next;
            }else{
                return head;
            }
        }
        return null;
    }

    //解法二：快慢指针
    //定理：如果快慢指针再环中相遇，此时快指针来到head处，慢指针再环中相遇处
    //一步一步走必再第一个相交节点相遇
    public ListNode detectCycle2(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        ListNode slow = head.next;  //慢指针
        ListNode fast = head.next.next;  //快指针
        //快指针和慢指针再环中相遇地点
        while (slow != fast) {
            if (fast.next == null || fast.next.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        //快指针来到头节点  然后开始和慢指针同步移动  一步一步移动
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}
